package main

import (
	"fmt"
)

func selectSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		// 每次选择出最大或者最小的
		for j := i + 1; j < len(arr); j++ {
			if arr[i] > arr[j] {
				arr[i], arr[j] = arr[j], arr[i]
			}
		}
	}
}

func optimizeSelectSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		minOrMaxIndex := i
		for j := i + 1; j < len(arr); j++ {
			if arr[j] < arr[minOrMaxIndex] {
				minOrMaxIndex = j
			}
		}
		// 找出最大或者最小，循环一次换一次
		arr[i], arr[minOrMaxIndex] = arr[minOrMaxIndex], arr[i]
	}
}

func bubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
			}
		}
	}
}

func optimizeBubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		flag := true
		// 记录是否发生交换
		for j := 0; j < len(arr)-i-1; j++ {
			if arr[j] > arr[j+1] {
				arr[j], arr[j+1] = arr[j+1], arr[j]
				flag = false
			}
		}
		if flag {
			break
		}
	}
}

func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}
	left := []int{}
	mid := []int{}
	right := []int{}
	pivot := arr[len(arr)/2]
	for _, v := range arr {
		if v < pivot {
			left = append(left, v)
		} else if v > pivot {
			right = append(right, v)
		} else {
			mid = append(mid, v)
		}
	}
	return append(append(quickSort(left), mid...), quickSort(right)...)
}

func main() {
	arr := []int{5, 2, 8, 6, 3, 9, 1, 7, 4}
	// optimizeSelectSort(arr)
	// bubbleSort(arr)
	// optimizeBubbleSort(arr)
	sortArr := quickSort(arr)
	fmt.Println(arr)
	fmt.Println(sortArr)
}
